package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/7 14:47
 * @Version 1.0
 **/
public class LetterTilePossibilities {
    int M = 26;
    int[] dp = new int[M];
    int result = 0;
    public int numTilePossibilities(String tiles) {
        int len = tiles.length();
        for (int i = 0; i < len; i++) {
            dp[tiles.charAt(i) - 'A']++;
        }
        result = getResult();
        return result;
    }

    /**
     * 使用如下算法  不会出现 AAB -> A1B\A2B  的情况
     * dfs+Set去重  --估计会超时，效率也低
     * @return
     */
    private int getResult() {
        for (int i = 0; i < M; i++) {
            if (dp[i] > 0) {
                dp[i]--;
                result++;
                result += getResult();
                dp[i]++;
            }
        }
        return result;
    }
}
